#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2020-07-24 9:47 上午
# @Author  : yangdy
# @File    : 2020-07-24.1025.除数博弈
# @Software: PyCharmCE


class Solution:
    def divisorGame(self, N: int) -> bool:
        ans = False
        # 1.偶数必胜，奇数必败
        # ans = N % 2 == 0
        # 2. 状态转移 m(x)
        m = [False for i in range(N+2)]
        m[0], m[1], m[2] = False, False, True
        for i in range(3, N+1):
            for j in range(1, i):
                if i % j == 0 and m[i-j] is False:
                    m[i] = True
                    break
        ans = m[N]
        return ans


solve = Solution()

questions = [
    (2, ),
    (3, ),
    (4, ),
]

for qi, q in enumerate(questions):
    print(f'#{qi}:', q)
    print(solve.divisorGame(q[0]))
